package dp;

public class LintCode125 {
    public int backPackII(int m, int[] A, int[] V) {
        //二维数组解决
        int n=A.length;
        int[][] maxValue=new int[n+1][m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                if(A[i-1]<=j){
                    maxValue[i][j]=Math.max(maxValue[i-1][j],maxValue[i-1][j-A[i-1]]+V[i-1]);
                }else {
                    maxValue[i][j]=maxValue[i-1][j];
                }
            }
        }
        return maxValue[n][m];


        //一维数组
//        int n=A.length;
//        int[] maxValue=new int[m+1];
//        for (int i = 1; i <=n ; i++) {
//            for (int j = m; j > 0 ; j--) {
//                if(A[i-1]<=j){
//                    maxValue[i]=Math.max(maxValue[j],maxValue[j-A[i-1]]+V[i-1]);
//                }
//            }
//        }
//        return maxValue[m];
    }
}
